package com.hot100;

import java.util.Arrays;
import java.util.Collections;

//https://leetcode.cn/problems/permutation-sequence/solutions/285250/pai-lie-zu-he-zhi-di-kge-pai-lie-golden-monkey-by-/
public class Solution31 {
    public void nextPermutation(int[] nums) {
        int index = nums.length - 1;
        int flag = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                while (index > i && nums[index] <= nums[i - 1]) index--;
                nums[index] = nums[i - 1] ^ nums[index];
                nums[i - 1] = nums[i - 1] ^ nums[index];
                nums[index] = nums[i - 1] ^ nums[index];
                Arrays.sort(nums, i, nums.length);
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            for (int i = 0, j = nums.length - 1; i < j; i++, j--) {
                nums[i] = nums[i] ^ nums[j];
                nums[j] = nums[i] ^ nums[j];
                nums[i] = nums[i] ^ nums[j];
            }
        }
    }
}
